P3345 [ZJOI2015]幻想乡战略游戏

发表于

闲扯

感觉这题基本就是看的题解，不过还是大概对动态点分治有了些了解吧，决定还是写篇题解记录一下。

题面

P3345 [ZJOI2015]幻想乡战略游戏

Solution

先考虑给出每个点的军队个数怎么办。

我们考虑通过换根 $DP$ 的方式来求解。

具体的，我们设 $sz_u$ 表示 $u$ 的子树中军队个数， $dp_u$ 表示以 $u$ 为根结点时的答案。

考虑换根过程，当前节点为 $u$ ，要换到 $v$ 时，我们有：

可以知道，如果 $dp_vsz_u$ ，否则答案一定不优。容易证明，对于每一个点 $u$ ，这样的 $v$ 只有一个。

那么现在要加上修改呢？

这时候就要引进一个黑科技：动态点分治。

动态点分治又称点分树。具体来讲，就是将点分治过程中找出的重心对应连边，最后得到一个树高为 $\log$ 的新树。

我们在这棵树上暴力向上跳，然后 $O(1)$ 或 $O(\log)$ 的进行对每个点的答案的操作，就能保证复杂度为 $O(n\log n)$ 或者 $O(n\log^2 n)$ 。

我们考虑怎么利用这个点分树来维护我们的信息。

这时，我们又要提到一个动态点分治中很重要的思想：维护儿子，维护父亲。

具体的，对这道题来讲，我们维护 $3$ 个数组： $dis1_u,dis2_u,sum_u$ ，分别表示点分树中 $u$ 的子树中的点对 $u$ 的贡献，对 $fa_u$ 的贡献以及子树中的军队数。

考虑怎么计算一个点 $u$ 的答案。

还是类似换根时的想法，我们考虑在点分树上暴力往上跳。

我们设最初的答案 $ans=dis1_u$ 。

然后从 $u$ 开始考虑到根结点的链上的每个点（根结点除外）。

假设当前在 $v$ 点，那么对答案的贡献为 $dis1_{fa_v}-dis2_v+dis_{v,fa_v}\cdot(sum_{fa_v}-sum_v)$ 。

这个画个图大概就能理解了。

然后考虑修改。

类似的，我们也只需要考虑从 $u$ 开始到根结点的链上的每个点（根结点除外），算出对 $dis1_{fa_v},dis2_v$ 的贡献即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int MAXN = 1e5+5;
int n,m,u,v,d,head[MAXN],num_edge;
ll dis1[MAXN],dis2[MAXN],sum[MAXN];
char vis[MAXN];
struct Edge{
	int next,to,w;
	Edge(){}
	Edge(int next,int to,int w):next(next),to(to),w(w){}
}edge[MAXN<<1];
il add_edge(int u,int v,int w){
	edge[++num_edge]=Edge(head[u],v,w),head[u]=num_edge;
	edge[++num_edge]=Edge(head[v],u,w),head[v]=num_edge;
}
struct Graph{
	int head[MAXN],num_edge;
	struct Edge{
		int next,to,dis;
		Edge(){}
		Edge(int next,int to,int dis):next(next),to(to),dis(dis){}
	}edge[MAXN<<1];
	il add_edge(int u,int v,int dis){
		edge[++num_edge]=Edge(head[u],v,dis),head[u]=num_edge;
		edge[++num_edge]=Edge(head[v],u,dis),head[v]=num_edge;
	}
	int f[MAXN],top[MAXN],son[MAXN],sz[MAXN],dep[MAXN],dis[MAXN];
	il DFS1(int u,int fa){
		f[u]=fa,sz[u]=1,dep[u]=dep[fa]+1;
		for(ri i=head[u];i;i=edge[i].next){
			if(edge[i].to==fa) continue;
			dis[edge[i].to]=dis[u]+edge[i].dis,DFS1(edge[i].to,u),sz[u]+=sz[edge[i].to];
			if(sz[edge[i].to]>sz[son[u]]) son[u]=edge[i].to;
		}
	}
	il DFS2(int u,int t){
		top[u]=t;
		if(!son[u]) return ;
		DFS2(son[u],t);
		for(ri i=head[u];i;i=edge[i].next){
			if(edge[i].to==f[u]||edge[i].to==son[u]) continue;
			DFS2(edge[i].to,edge[i].to);
		}
	}
	it LCA(int u,int v){
		while(top[u]!=top[v]){
			if(dep[top[u]]<dep[top[v]]) swap(u,v);
			u=f[top[u]];
		}
		return dep[u]<dep[v]?u:v;
	}
	it Query(int x,int y){return dis[x]+dis[y]-2*dis[LCA(x,y)];}
	il Init(){
		for(ri i=1;i<n;++i)
			read(u),read(v),read(d),add_edge(u,v,d);
		DFS1(1,0),DFS2(1,1);
	}
}G;
int S,mx,rt,sz[MAXN],fa[MAXN];
il Get_Rt(int u,int fa){
	sz[u]=1;int mx1=0;
	for(ri i=G.head[u];i;i=G.edge[i].next){
		if(G.edge[i].to==fa||vis[G.edge[i].to])
			continue;
		Get_Rt(G.edge[i].to,u),sz[u]+=sz[G.edge[i].to];
		mx1=max(mx1,sz[G.edge[i].to]);
	}
	mx1=max(mx1,S-sz[u]);
	if(mx1<mx)
		mx=mx1,rt=u;
}
il Solve(int u){
	vis[u]=1;
	for(ri i=G.head[u];i;i=G.edge[i].next){
		if(vis[G.edge[i].to])
			continue;
		S=sz[G.edge[i].to],mx=INF,Get_Rt(G.edge[i].to,u);
		fa[rt]=u,add_edge(u,rt,G.edge[i].to),Solve(rt);
	}
}
il Updata(int u,int k){
	sum[u]+=k;
	for(ri i=u;fa[i];i=fa[i]){
		int dist=G.Query(fa[i],u);
		dis1[fa[i]]+=1ll*dist*k;
		dis2[i]+=1ll*dist*k;
		sum[fa[i]]+=k;
	}
}
ill Calc(int u){
	ll ans=dis1[u];
	for(ri i=u;fa[i];i=fa[i]){
		int dist=G.Query(fa[i],u);
		ans+=dis1[fa[i]]-dis2[i];
		ans+=dist*(sum[fa[i]]-sum[i]);
	}
	return ans;
}
ill Query(int u){
	ll ans=Calc(u);
	for(ri i=head[u];i;i=edge[i].next){
		ll tmp=Calc(edge[i].w);
		if(tmp<ans) return Query(edge[i].to);
	}
	return ans;
}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	read(n),read(m),G.Init();
	S=n,mx=INF,Get_Rt(1,0);
	int tmp=rt;Solve(rt),rt=tmp;
	for(ri i=1;i<=m;++i){
		read(u),read(d),Updata(u,d);
		print(Query(rt)),puts("");
	}
	return 0;
}